package io.huaguoguo;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Title:
 * @Description: 算法题
 * @author: huaguoguo
 * @Date： 2021/6/9 18:22
 */
@Slf4j
public class MathTests {

    /**
     * 斐波拉切数列计算第N项
     */
    @Test
    public void fibonacci() {

    }

    int n = 10;
    int[] f = new int[n + 1];

    /**
     * 青蛙跳台阶问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * 循环解法
     */
    @Test
    public void test1() {
        test1_1();
        log.info("循环解法" + Arrays.toString(f));
        f = new int[n + 1];
        test1_2();
        log.info("递归解法" + Arrays.toString(f));
    }


    /**
     * 循环解法
     */
    public void test1_1() {
        // 跳1个台阶的跳法
        int f1 = 1;
        // 跳2个台阶的跳法
        int f2 = 2;
        // 跳n个 = f(n-1) + f(n-2)
        f[1] = 1;
        f[2] = 2;
        int fn = 0;
        for (int i = 3; i <= n; i++) {
            fn = f1 + f2;
            f1 = f2;
            f2 = fn;
            f[i] = fn;
        }
    }


    /**
     * 递归解法
     */
    public void test1_2() {
        calc(n);
    }

    public int calc(int n) {
        if (n == 1 || n == 2) {
            return f[n] = n;
        }
        int fn = calc(n - 1) + calc(n - 2);
        return f[n] = fn;
    }

    /////////////////////////////////////////////


    /**
     * 变态跳台阶问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
     * 假设n>=2，第一步有n种跳法：跳1级、跳2级、到跳n级 跳1级，剩下n-1级，则剩下跳法是f(n-1) 跳2级，剩下n-2级，
     * 则剩下跳法是f(n-2) ...... 跳n-1级，剩下1级，则剩下跳法是f(1) 跳n级，剩下0级，则剩下跳法是f(0)
     * 所以在n>=2的情况下：
     * f(n)=f(n-1)+f(n-2)+...+f(1)
     * 因为f(n-1)=f(n-2)+f(n-3)+...+f(1)
     * 所以f(n)=2*f(n-1) 又f(1)=1,所以可得f(n)=2^(number-1)
     */
    @Test
    public void test2() {
        for (int i = 0; i <= n; i++) {
            f[i] = 1 << i;
        }
        log.info("变态跳台阶问题" + Arrays.toString(f));
    }

    /**
     * 链表中倒数第k个节点
     * 输入一个链表，输出该链表中倒数第k个结点
     * 思路: 两个指针一个指针p1先开始跑，指针p1跑到k-1个节点后，另一个节点p2开始跑，当p1跑到最后时，p2所指的指针就是倒数第k个节点。
     */
    @Test
    public void test3() {
        int k = 3;
        LinkedList<Integer> links = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            links.add(i);
        }
        // 初始都指向0
        int p1 = 0, p2 = 0;
        for (Integer link : links) {
            if (p1 > (k - 1)) {
                p2++;
            }
            p1++;
        }
        log.info("链表：" + links.toString());
        log.info("第" + p2 + "个节点是链表的倒数第" + k + "个节点");
    }

    /**
     *  反转链表
     *  输入一个链表，反转链表后，输出链表的所有元素。
     */
    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    @Test
    public void test4() {
        ListNode listNode = new ListNode(0);
        ListNode lastNode = listNode;
        for (int i = 1; i < 10; i++) {
            lastNode.next = new ListNode(i);
            lastNode = lastNode.next;
        }

        ListNode head = listNode;
        ListNode next = null;
        // 反转的链表
        ListNode pre = null;
        // 0-1-2-3-4
        while (head != null) {
            //保存要反转到头来的那个节点
            next = head.next;
            //要反转的那个节点指向已经反转的上一个节点
            head.next = pre;
            //上一个已经反转到头部的节点
            pre = head;
            //一直向链表尾走
            head = next;
        }

        ListNode eachLink = pre;
        do {
            log.info(String.valueOf(eachLink.val));
            eachLink = eachLink.next;
        } while (eachLink != null);
    }
}
